#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title06最大报酬.py 
@version:
@time: 2023/05/31
https://dream.blog.csdn.net/article/details/129052681
工作时长 工作数量
消耗时长 报酬

40 3
20 10
20 20
20 5

30

"""
def solve_method(jobs, t):
    if t <= 0:
        return 0
    min_time = min(jobs, key=lambda x: x[0])[0]
    dp = [[0] * (t + 1) for _ in range(len(jobs) + 1)]
    for i in range(1, len(jobs) + 1):
        for j in range(min_time, t + 1):
            job = jobs[i - 1]
            v = dp[i - 1][j]
            new_v = job[1] + dp[i - 1][j - job[0]] if job[0] <= j else 0
            dp[i][j] = max(v, new_v)
    return dp[len(jobs)][t]


if __name__ == "__main__":
    T, n = map(int, input().split())
    jobs = [list(map(int, input().split())) for _ in range(n)]
    res = solve_method(jobs, T)
    print(res)
